package leetcode.code1337;

import java.util.PriorityQueue;

/**
 *
 * @author Max
 * @date 2021年8月26日
 * @description
 */
public class Solution3 extends Solution1337 {

	@Override
	public int[] kWeakestRows(int[][] mat, int k) {
		// 0 下标， 1战斗力
		PriorityQueue<int[]> p = new PriorityQueue<>((m, n) -> {
			if ((m[1] < n[1]) || (m[1] == n[1] && m[0] < n[0]))
				return 1;
			return -1;
		});
		for (int i = 0; i < mat.length; i++) {
			int l = 0;
			int r = mat[i].length;
			int m = (r - l) / 2 + l;
			while (l < r) {
				if (mat[i][m] == 1) {
					l = m + 1;
				} else {
					r = m;
				}
				m = (r - l) / 2 + l;
			}
			if (p.size() == k && p.peek()[1] > l) {
				p.poll();
				p.add(new int[] { i, l });
			} else if (p.size() < k) {
				p.add(new int[] { i, l });
			}
		}
		int[] result = new int[k];
		for (int i = k - 1; i >= 0; i--) {
			result[i] = p.poll()[0];
		}
		return result;
	}

	public static void main(String[] args) {
		Solution3 so = new Solution3();
		so.debug1();
		so.debug2();
	}

}
